package greddy;

import java.util.Arrays;

public class _07_1005_K次取反后最大化的数组和 {
    public static int largestSumAfterKNegations(int[] nums, int k) {

    	// 排序后，先对最小的负数取反
    	// 如果全部负数取反完，k还有剩余，则取最小的值进行取反
    	Arrays.sort(nums);
    	for(int i = 0 ; i < nums.length && k > 0; i++) {	
    		if(nums[i] < 0) {
    			nums[i] = -nums[i];
    			k--;
    		}else {
    			// nums[i] >= 0 说明后面的都>=0，不必再循环
    			break;
    		}
    	}
    	
    	if(k > 0 && k % 2 == 1) {
    		Arrays.sort(nums);
    		nums[0] = -nums[0];
    	}
    	int sum = 0;
    	for(int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    	}
    	
    	return sum;
    }
    public static void main(String[] args) {
    	int[] nums = {1};
    	System.out.println(largestSumAfterKNegations(nums, 3));
	}
}
